package org.raymond.iworks.study.basic.structure.queue;

/**
 * 普通数组:
 * front:指向队列的第一个元素的前一个元素,这个"前一个元素"已被弹出,或不存在
 * tail:指向队列的最后一个元素,这个"最后一个元素"在初始化时没有值,后续随着添加数据才有值
 * 普通数组思路分析:
 * 1, 判断为满的条件: 最后一个元素在最大下标处,即tail==max-1
 * 2, 判断为空的条件: 参考front定义, 即array[front]==null, 当front==tail, 表示队列已空
 * 环形数组队列功能描述:
 *     在普通数组队列的基础上,使数组元素满后,再剔除第一个元素后,能够继续在队列尾部添加新的元素
 * 环形数组指针定义:
 * front: 指向队列的第一个元素.这个元素的数组下标为front
 * tail: 指向队列的最后一个元素,这个元素的数组下标为tail-1
 * 环形数组队列思路分析:
 * 1, 判断为满的条件:
 * 分析:
 * 1.1, 环形数组满的时候,考虑在一个环中(形象思维),假设front的位置是a,则tail的位置是a-1.
 * 1.2, 从%的角度看,(a-1+1)%max=a,即(tail+1)%max==front
 * 1.3, 从循环的角度看,逻辑上需要一个位置即代表队列头,也代表队列尾,这样才能循环起来.
 * 但是不能直接用front==tail,因为这个条件需要用来判空,如果用tail%max==front来判满,在初始化时判断结果front==tail永远为真,就没有意义了.
 * 因此用(tail+1)%max==front来判满,这里就需要额外多出一个空格出来,这个空格用来保存队列最后一个元素的后一个位置,也是队列第一个元素之前的一个位置
 * 即这个位置在front之前,tail之后.
 * 这个空格就是(tail+1)%max==front中的1.这个空格不保存任何值,仅仅用来衔接队列头和队列尾.考虑到tail实际的数组下标为tail-1,因此这个空格的数组下标就是tail
 * 因此,front指向队列的第一个元素,初始化为0,tail-1指向队列的最后一个元素,tail指向队列的最后一个元素的后一个位置,也初始化为0.
 * 即初始化时,front指向空格,表示队列为空.
 * 队列非空时,多次调用pop后,front从tail-1(此时有数据)的位置上再次pop,front移动到了tail,即front==tail,此时队列又空了.
 * 因此,当front==tail,这两个自定义的指针同时指向空格,表示队列为空
 * 在有了这个多出来的空格后,max就不再表示逻辑最大元素数,而是包括了空格的实际最大元素数.逻辑的最大元素数为max-1
 * 2, 判断为空的条件: front==tail
 * 3, 队列长度: (tail+max-front)%max
 * 注意:由于支持循环,起始位置不再是固定的0,而应该是front,
 * 同理,当tail到下一轮,front还在上一轮时,可能存在tail<front,这时若他们之间直接的差值不能与一轮的长度正确对应,需要加max来获得正确的差值
 *
 * 第一轮直接加满
 * arr[0]=1 => front=0
 * arr[1]=2
 * arr[2]=3
 * arr[3]=4
 * arr[4]=5 => tail=5
 * arr[5]=已满,无法再加
 *
 * pop调用4次
 * h=> head=5
 * t=> tail=5
 * front=4, tail=5
 *
 * pop调用第5次
 * 队列已空
 *
 * a 6
 * h=> head=6
 * t=> tail=6
 * front=5, tail=0
 *
 * 总结:
 * 从程序的角度来讲,这里多出来的空格是用来保存下一个元素的.
 * 生活中可以参考表盘,0和12指向同一个位置,但其实是两个数据,1个是第一天的最后一个时刻,另一个是第二天的最开始的时刻.
 * 但我们用代码实现的时候,程序是理解不了这种场景的,我们必须为两个不同的数据腾出两个数组位置出来.
 * 比如一个队列最大长度为5,写满后为1,2,3,4,5.这时我们要复用队列,且满足FIFO,就必须先删除第一个元素,删除后就是[],2,3,4,5. ([]表示数组元素为空,下同).
 * 但是队列是线性的,我们不能直接在第一个数组位置上写入数据,比如写成6,2,3,4,5,这样程序没法判断这个队列到底是从6开始,还是从2开始.
 * 所以我们要在原来长度为5的数组上增加一个位置,把新增的数据加到队列尾部,即写成这样:[],2,3,4,5,6.这样程序就能理解这个队列是从2开始,到6结束.
 * 如果需要再次增加一个数据,则还是要先删第一个元素,为:[],[],3,4,5,6.接着增加下一个元素,就是:7,[],3,4,5,6.
 * 这里,空格就起到标志开头和结尾的作用,[]之前是尾部,[]之后是头部.
 */
public class CircleQueue<E> {
    // 数组最大容量
    private int max;
    // 指向队列第一个元素所在的位置
    private int front;
    // 指向队列最后一个元素的后一个位置,以便空出一个空位.
    private int tail;
    // 存放数据的数组
    private Object[] array;

    public CircleQueue(int max){
        this.max = max;
        array = new Object[max];
        front = 0;
        tail = 0;
    }

    // 判断队列是否已满
    public boolean isFull(){
        // 逻辑上,这里的1是同时连接tail与front的公共空格,不占数据
        return (tail+1)%max==front;
    }
    // 判断队列是否为空
    public boolean isEmpty(){
        // 逻辑上,这里front与tail都同时减去了一个用于连接的公共空格
        return front == tail;
    }
    // 添加数据到队列
    public void add(E e){
        if(isFull()) {
            System.out.println("队列已满,不能加入数据");
            return;
        }
        // tail表示最后一个元素的后一个位置,因此这里直接写到tail位上,
        // 就是在队列尾部插入新数据了
        array[tail] = e;
        // 再将tail后移,使tail继续指向最后一个元素的后一个位置.
        // 这里需要取模,这是循环队列,防止越界
        tail=(tail+1)%max;
    }
    // 数据出队列
    public E pop(){
        if(isEmpty()){
            System.out.println("队列已空,没有数据可以获取");
            return null;
        }
        // front表示队列中的第一个元素所在的位置,即array[front]
        E tmp = (E)array[front];
        // 再将front后移,需要取模,这是循环队列,防止越界
        front=(front+1)%max;
        // 如果先将front后移,再用array[front]取数据,那么读到的就是第二个数据,而不是第一个
        // ++的优先级高于[]
        return tmp;
    }
    public void showAll(){
        if(isEmpty()){
            System.out.println("队列已空,没有数据可以展示");
            return;
        }
        StringBuilder dataBuilder = new StringBuilder();
        for(int i=front; i<front+size(); i++){
            dataBuilder.append("array[").append(i%max).append("]=")
                    .append(array[i%max].toString()).append("\n");
        }
        String data = dataBuilder.toString();
        System.out.println("data:\n" + data);
    }
    public E peekHead(){
        if(isEmpty()){
            System.out.println("队列已空,没有数据可以peek");
            return null;
        }
        // 只返回第一个元素,不需要移动位置
        return (E)array[front];
    }

    public E peekTail(){
        if(isEmpty()){
            System.out.println("队列已空,没有数据可以peek");
            return null;
        }
        // 只返回最后一个元素,不需要移动位置
        return (E)array[(tail+max-1)%max];
    }

    public int size(){
        return (tail+max-front)%max;
    }
}
